home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C++ / Libraries / KPlib 1.2.1 / KPList.h < prev    next >
Encoding:
Text File  |  1994-11-07  |  45.9 KB  |  963 lines  |  [TEXT/R*ch]
  1. or and operator=().
  2.  
  3. template <class Element>
  4. class KPList {
  5.         friend class KPReadOnlyIterator<Element>;
  6.         friend class KPIterator<Element>;
  7.     public:
  8.         KPList();
  9.         KPList(const KPList &list);
  10.         KPList(const Element &element);
  11.         virtual ~KPList();
  12.         KPList operator+(const KPList &list);
  13.         KPList operator+(const Element &element);
  14.         void operator+=(const KPList &list);
  15.         void operator+=(const Element &element);
  16.         KPList &operator=(const KPList &list);
  17.         KPList &operator=(const Element &element);
  18.         Element &head();
  19.         Element &tail();
  20.         const Element &head() const;
  21.         const Element &tail() const;
  22.         void add_to_head(const Element &element);
  23.         void add_to_tail(const Element &element);
  24.         void remove_head();
  25.         void remove_tail();
  26.         Element &operator[](int index);
  27.         const Element &operator[](int index) const;
  28.         int size() const;
  29.         bool is_empty() const;
  30.         void clear();
  31.         KPList all_such_that(bool (*f)(const Element &)) const;
  32.  
  33.     protected:
  34.         struct Node {
  35.             Element element;
  36.             Node *previous;
  37.             Node *next;
  38.         };
  39.         virtual void error(const char *msg) const;
  40.         int my_size;
  41.         unsigned int my_iterator_count;
  42.         Node *my_head;
  43.         Node *my_tail;
  44. };
  45.  
  46. // Assumes Element has the above plus operator==().
  47.  
  48. template <class Element>
  49. class KPComparableList: public KPList<Element> {
  50.     public:
  51.         KPComparableList();
  52.         KPComparableList(const KPComparableList &list);
  53.         KPComparableList(const KPList<Element> &list);
  54.         KPComparableList(const Element &element);
  55.         virtual ~KPComparableList();
  56.         KPComparableList &operator=(const KPList<Element> &list);
  57.         KPComparableList &operator=(const Element &element);
  58.         KPComparableList operator+(const KPList<Element> &list);
  59.         KPComparableList operator+(const Element &element);
  60.         KPComparableList operator-(const KPComparableList &list);
  61.         KPComparableList operator-(const Element &element);
  62.         void operator-=(const KPComparableList &list);
  63.         void operator-=(const Element &element);
  64.         bool operator==(const KPComparableList &list) const;
  65.         bool operator!=(const KPComparableList &list) const;
  66.         bool contains(const KPComparableList &list) const;
  67.         bool contains(const Element &element) const;
  68.         int occurrences_of(const Element &element) const;
  69.         void clear();
  70.         void clear(const Element &element);
  71.         void clear(const KPComparableList &list);
  72.     protected:
  73.         virtual void error(const char *msg) const;
  74. };
  75.  
  76. // Assumes Element has the above plus operator<().  Note that this operator
  77. // must place a total ordering on the set of Elements.
  78.  
  79. template <class Element>
  80. class KPSortableList: public KPComparableList<Element> {
  81.     public:
  82.         KPSortableList();
  83.         KPSortableList(const KPSortableList &list);
  84.         KPSortableList(const KPList<Element> &list);
  85.         KPSortableList(const Element &element);
  86.         virtual ~KPSortableList();
  87.         KPSortableList &operator=(const KPList<Element> &list);
  88.         KPSortableList &operator=(const Element &element);
  89.         void sort();
  90.         Element &min();
  91.         const Element &min() const;
  92.         Element &max();
  93.         const Element &max() const;
  94.     protected:
  95.         virtual void error(const char *msg) const;
  96.         static int findpivot(int i, int j, Element **elementlist);
  97.         static int partition(int l, int r, const Element &pivot,
  98.                                                     Element **elementlist);
  99.         static void quicksort(int i, int j, Element **elementlist);
  100. };
  101.  
  102. // A list keeps track of the number of iterators iterating over it.  Rules:
  103. //
  104. //    - If a list has no iterators, one can add to and remove from that
  105. //      list without restriction.
  106. //
  107. //    - If a list has one iterator, one can add to and remove elements from
  108. //      the list through the iterator without restriction, although one
  109. //      cannot remove elements from the list directly.
  110. //
  111. //    - If a list has more than one iterator, one cannot remove elements
  112. //      from the list at all.
  113. //
  114. // As a result, if a list goes out of scope while there is still an
  115. // iterator attached to it, this is an error.  Usually the declaration of
  116. // an iterator appears after the declaration of the list it is to iterate
  117. // over (or it is in a more local scope), so this is usually not a problem
  118. // (since it's destructor is called first, detaching it implicitly).  To
  119. // detach an iterator from a list explicitly, call iterate_over().
  120.  
  121. // Use KPReadOnlyIterator if you wish to iterate over a const KPList or if you
  122. // do not intend to modify the list through the iterator.
  123.  
  124. template <class Element>
  125. class KPReadOnlyIterator {
  126.     public:
  127.         KPReadOnlyIterator();
  128.         KPReadOnlyIterator(const KPList<Element> &list);
  129.         KPReadOnlyIterator(const KPReadOnlyIterator &iterator);
  130.         ~KPReadOnlyIterator();
  131.         KPReadOnlyIterator &iterate_over(const KPList<Element> &list);
  132.         KPReadOnlyIterator &iterate_over();
  133.         KPReadOnlyIterator &operator=(const KPReadOnlyIterator &iterator);
  134.         const Element ¤t() const;
  135.         const Element *KPReadOnlyIterator::ptr() const;
  136.         KPReadOnlyIterator &beginning();
  137.         KPReadOnlyIterator &end();
  138.         KPReadOnlyIterator &operator++();  // Prefix
  139.         KPReadOnlyIterator &operator--();  // Prefix
  140.         void operator++(int);            // Postfix
  141.         void operator--(int);            // Postfix
  142.         const Element &operator*() const;
  143.         const Element *operator->() const;
  144.         bool at_beginning() const;
  145.         bool at_end() const;
  146.         int size() const;
  147.         bool is_empty() const;
  148.         const KPList<Element> &list() const;
  149.     protected:
  150.         static void error(const char *msg);
  151.         const KPList<Element> *my_list;
  152.         const KPList<Element>::Node *my_current;
  153. };
  154.  
  155. // The rules defining what happens when odd combinations of element
  156. // removals and insertions are performed are fairly intuitive.  An element
  157. // can be deleted while the list is being parsed, and the parse can
  158. // continue.  Just don't try to access an element after it has been
  159. // deleted!  Once the iterator leaves a deleted element, it will not return
  160. // to it.
  161.  
  162. template <class Element>
  163. class KPIterator {
  164.     public:
  165.         KPIterator();
  166.         KPIterator(KPList<Element> &list);
  167.         KPIterator(const KPIterator &iterator);
  168.         ~KPIterator();
  169.         KPIterator &iterate_over(KPList<Element> &list);
  170.         KPIterator &iterate_over();
  171.         KPIterator &operator=(const KPIterator &iterator);
  172.         KPIterator &insert_before_current(const Element &element);
  173.         KPIterator &insert_after_current(const Element &element);
  174.         KPIterator &replace_current_with(const Element &element);
  175.         Element ¤t();
  176.         Element *KPIterator::ptr();
  177.         Element remove_current();
  178.         KPIterator &beginning();
  179.         KPIterator &end();
  180.         KPIterator &operator++();  // Prefix
  181.         KPIterator &operator--();  // Prefix
  182.         void operator++(int);    // Postfix
  183.         void operator--(int);    // Postfix
  184.         Element &operator*();
  185.         Element *operator->();
  186.         bool at_beginning() const;
  187.         bool at_end() const;
  188.         int size() const;
  189.         bool is_empty() const;
  190.         KPList<Element> &list();
  191.     protected:
  192.         static void error(const char *msg);
  193.         KPList<Element> *my_list;
  194.         KPList<Element>::Node my_deleted;
  195.         KPList<Element>::Node *my_current;
  196. };
  197.  
  198. // The following macro is defined as a convenience.  Here is an example of
  199. // its usage:
  200. //
  201. //     KPSortableList<int> intlist;
  202. //     intlist += 42;
  203. //     intlist += 11;
  204. //     intlist += 76;
  205. //     intlist += 9;
  206. //     intlist.sort();
  207. //
  208. //     KPReadOnlyIterator<int> iter(intlist);
  209. //     FOREACH(iter) cout << *iter << '\n';
  210.  
  211. #define FOREACH(iter) for (iter.beginning(); iter.ptr(); iter++)
  212.  
  213. /****************************************************************************/
  214.  
  215. template <class Element>
  216. inline
  217. KPList<Element>::KPList()
  218. {
  219.     my_size = my_iterator_count = 0;
  220.     my_head = my_tail = NULL;
  221. }
  222.  
  223. /****************************************************************************/
  224.  
  225. template <class Element>
  226. inline
  227. KPList<Element>::KPList(const KPList<Element> &list)
  228. {
  229.     my_size = my_iterator_count = 0;
  230.     my_head = my_tail = NULL;
  231.     *this = list;
  232. }
  233.  
  234. /****************************************************************************/
  235.  
  236. template <class Element>
  237. inline
  238. KPList<Element>::KPList(const Element &element)
  239. {
  240.     my_size = my_iterator_count = 0;
  241.     my_head = my_tail = NULL;
  242.     *this = element;
  243. }
  244.  
  245. /****************************************************************************/
  246.  
  247. template <class Element>
  248. inline
  249. KPList<Element>::~KPList()
  250. {
  251.     if (my_iterator_count > 0)
  252.         error("~KPList() - cannot destroy, iterators present");
  253.  
  254.     clear();
  255. }
  256.  
  257. /****************************************************************************/
  258.  
  259. template <class Element>
  260. inline KPList<Element>
  261. KPList<Element>::operator+(const KPList<Element> &list)
  262. {
  263.     KPList<Element> new_list(*this);
  264.     new_list += list;
  265.     return new_list;
  266. }
  267.  
  268. /****************************************************************************/
  269.  
  270. template <class Element>
  271. inline KPList<Element>
  272. KPList<Element>::operator+(const Element &element)
  273. {
  274.     KPList<Element> new_list(*this);
  275.     new_list += element;
  276.     return new_list;
  277. }
  278.  
  279. /****************************************************************************/
  280.  
  281. template <class Element>
  282. void
  283. KPList<Element>::operator+=(const KPList<Element> &list)
  284. {
  285.     const Node *node;
  286.     const int size = list.my_size;
  287.     int i;
  288.  
  289.     // Must use size as stopping condition in case *this == list.
  290.     for (node = list.my_head, i=0; i < size; node = node->next, i++)
  291.         *this += node->element;
  292. }
  293.  
  294. /****************************************************************************/
  295.  
  296. template <class Element>
  297. void
  298. KPList<Element>::operator+=(const Element &element)
  299. {
  300.     Node *newnode = new Node;
  301.     check_mem(newnode);
  302.     newnode->next = NULL;
  303.     newnode->element = element;
  304.     if (my_size++ == 0) {
  305.         my_head = newnode;
  306.         newnode->previous = NULL;
  307.     }
  308.     else {
  309.         my_tail->next = newnode;
  310.         newnode->previous = my_tail;
  311.     }
  312.     my_tail = newnode;
  313. }
  314.  
  315. /****************************************************************************/
  316.  
  317. template <class Element>
  318. KPList<Element> &
  319. KPList<Element>::operator=(const KPList<Element> &list)
  320. {
  321.     if (this == &list)
  322.         return *this;
  323.  
  324.     if (my_iterator_count > 0)
  325.         error("operator=() - cannot reassign, iterators present");
  326.  
  327.     Node *node, *newnode, *prevnode;
  328.  
  329.     clear();
  330.  
  331.     if (!(node = list.my_head))
  332.         return *this;
  333.  
  334.     newnode = new Node;
  335.     check_mem(newnode);
  336.     newnode->previous = NULL;
  337.     newnode->element = node->element;
  338.     my_head = prevnode = newnode;
  339.  
  340.     for (node = node->next; node; node = node->next) {
  341.         newnode = new Node;
  342.         check_mem(newnode);
  343.         newnode->element = node->element;
  344.         prevnode->next = newnode;
  345.         newnode->previous = prevnode;
  346.         prevnode = newnode;
  347.     }
  348.     newnode->next = NULL;
  349.     my_tail = newnode;
  350.     my_size = list.my_size;
  351.  
  352.     return *this;
  353. }
  354.  
  355. /****************************************************************************/
  356.  
  357. template <class Element>
  358. KPList<Element> &
  359. KPList<Element>::operator=(const Element &element)
  360. {
  361.     if (my_iterator_count > 0)
  362.         error("operator=() - cannot reassign, iterators present");
  363.  
  364.     clear();
  365.  
  366.     Node *newnode = new Node;
  367.     check_mem(newnode);
  368.     newnode->element = element;
  369.     newnode->previous = newnode->next = NULL;
  370.     my_head = my_tail = newnode;
  371.     my_size = 1;
  372.  
  373.     return *this;
  374. }
  375.  
  376. /****************************************************************************/
  377.  
  378. template <class Element>
  379. inline Element &
  380. KPList<Element>::head()
  381. {
  382.     if (!my_head)
  383.         error("head() - list is empty");
  384.  
  385.     return my_head->element;
  386. }
  387.  
  388. /****************************************************************************/
  389.  
  390. template <class Element>
  391. inline Element &
  392. KPList<Element>::tail()
  393. {
  394.     if (!my_tail)
  395.         error("tail() - list is empty");
  396.  
  397.     return my_tail->element;
  398. }
  399.  
  400. /****************************************************************************/
  401.  
  402. template <class Element>
  403. inline const Element &
  404. KPList<Element>::head() const
  405. {
  406.     if (!my_head)
  407.         error("head() - list is empty");
  408.  
  409.     return my_head->element;
  410. }
  411.  
  412. /****************************************************************************/
  413.  
  414. template <class Element>
  415. inline const Element &
  416. KPList<Element>::tail() const
  417. {
  418.     if (!my_tail)
  419.         error("tail() - list is empty");
  420.  
  421.     return my_tail->element;
  422. }
  423.  
  424. /****************************************************************************/
  425.  
  426. template <class Element>
  427. void
  428. KPList<Element>::add_to_head(const Element &element)
  429. {
  430.     Node *newnode = new Node;
  431.     check_mem(newnode);
  432.     newnode->element = element;
  433.     newnode->previous = NULL;
  434.     newnode->next = my_head;
  435.  
  436.     if (my_size++)
  437.         my_head->previous = newnode;
  438.     else
  439.         my_tail = newnode;
  440.     my_head = newnode;
  441. }
  442.  
  443. /****************************************************************************/
  444.  
  445. template <class Element>
  446. void
  447. KPList<Element>::add_to_tail(const Element &element)
  448. {
  449.     Node *newnode = new Node;
  450.     check_mem(newnode);
  451.     newnode->element = element;
  452.     newnode->previous = my_tail;
  453.     newnode->next = NULL;
  454.  
  455.     if (my_size++)
  456.         my_tail->next = newnode;
  457.     else
  458.         my_head = newnode;
  459.     my_tail = newnode;
  460. }
  461.  
  462. /****************************************************************************/
  463.  
  464. template <class Element>
  465. void
  466. KPList<Element>::remove_head()
  467. {
  468.     Node *old_head;
  469.  
  470.     if (my_iterator_count > 0)
  471.         error("remove_head() - cannot remove element, iterators present");
  472.  
  473.     if (old_head = my_head) {
  474.         if (old_head->next) {
  475.             old_head->next->previous = NULL;
  476.             my_head = old_head->next;
  477.         }
  478.         else
  479.             my_head = my_tail = NULL;
  480.  
  481.         delete old_head;
  482.         my_size--;
  483.     }
  484. }
  485.  
  486. /****************************************************************************/
  487.  
  488. template <class Element>
  489. void
  490. KPList<Element>::remove_tail()
  491. {
  492.     Node *old_tail;
  493.  
  494.     if (my_iterator_count > 0)
  495.         error("remove_tail() - cannot remove element, iterators present");
  496.  
  497.     if (old_tail = my_tail) {
  498.         if (old_tail->previous) {
  499.             old_tail->previous->next = NULL;
  500.             my_tail = old_tail->previous;
  501.         }
  502.         else
  503.             my_head = my_tail = NULL;
  504.  
  505.         delete old_tail;
  506.         my_size--;
  507.     }
  508. }
  509.  
  510. /****************************************************************************/
  511.  
  512. template <class Element>
  513. Element &
  514. KPList<Element>::operator[](int index)
  515. {
  516.     Node *node;
  517.  
  518.     if (index < 0 || index >= my_size)
  519.         error("operator[] - invalid index");
  520.  
  521.     node = my_head;
  522.     for (int i=0; i<index; i++)
  523.         node = node->next;
  524.  
  525.     return node->element;
  526. }
  527.  
  528. /****************************************************************************/
  529.  
  530. template <class Element>
  531. const Element &
  532. KPList<Element>::operator[](int index) const
  533. {
  534.     Node *node;
  535.  
  536.     if (index < 0 || index >= my_size)
  537.         error("operator[] - invalid index");
  538.  
  539.     node = my_head;
  540.     for (int i=0; i<index; i++)
  541.         node = node->next;
  542.  
  543.     return node->element;
  544. }
  545.  
  546. /****************************************************************************/
  547.  
  548. template <class Element>
  549. inline int
  550. KPList<Element>::size() const
  551. {
  552.     return my_size;
  553. }
  554.  
  555. /****************************************************************************/
  556.  
  557. template <class Element>
  558. inline bool
  559. KPList<Element>::is_empty() const
  560. {
  561.     return (my_size == 0);
  562. }
  563.  
  564. /****************************************************************************/
  565.  
  566. template <class Element>
  567. void
  568. KPList<Element>::clear()
  569. {
  570.     Node *nextnode;
  571.  
  572.     if (my_iterator_count > 0)
  573.         error("clear() - cannot clear, iterators present");
  574.  
  575.     for (Node *node = my_head; node; node = nextnode) {
  576.         nextnode = node->next;
  577.         delete node;
  578.     }
  579.     my_size = 0;
  580.     my_head = my_tail = NULL;
  581. }
  582.  
  583. /**********************************************ent>::KPIterator(const KPIterator<Element> &iterator)
  584. {
  585.     if (my_list = iterator.my_list)
  586.         my_list->my_iterator_count++;
  587.     my_current = iterator.my_current;
  588. }
  589.  
  590. /****************************************************************************/
  591.  
  592. template <class Element>
  593. inline
  594. KPIterator<Element>::~KPIterator()
  595. {
  596.     if (my_list)
  597.         my_list->my_iterator_count--;
  598. }
  599.  
  600. /****************************************************************************/
  601.  
  602. template <class Element>
  603. inline KPIterator<Element> &
  604. KPIterator<Element>::iterate_over(KPList<Element> &list)
  605. {
  606.     if (my_list)
  607.         my_list->my_iterator_count--;
  608.     my_list = &list;
  609.     my_list->my_iterator_count++;
  610.     my_current = my_list->my_head;
  611.  
  612.     return *this;
  613. }
  614.  
  615. /****************************************************************************/
  616.  
  617. template <class Element>
  618. inline KPIterator<Element> &
  619. KPIterator<Element>::iterate_over()
  620. {
  621.     if (my_list) {
  622.         my_list->my_iterator_count--;
  623.         my_list = NULL;
  624.         my_current = NULL;
  625.     }
  626.  
  627.     return *this;
  628. }
  629.  
  630. /****************************************************************************/
  631.  
  632.  
  633. template <class Element>
  634. inline KPIterator<Element> &
  635. KPIterator<Element>::operator=(const KPIterator &iterator)
  636. {
  637.     if (my_list)
  638.         my_list->my_iterator_count--;
  639.     if (my_list = iterator.my_list)
  640.         my_list->my_iterator_count++;
  641.     my_current = iterator.my_current;
  642.  
  643.     return *this;
  644. }
  645.  
  646. /****************************************************************************/
  647.  
  648. template <class Element>
  649. KPIterator<Element> &
  650. KPIterator<Element>::insert_before_current(const Element &element)
  651. {
  652.     if (!my_current)
  653.         error("insert_before_current() - no current element");
  654.  
  655.     KPList<Element>::Node *newnode = new KPList<Element>::Node;
  656.     check_mem(newnode);
  657.     newnode->element = element;
  658.  
  659.     if (my_current->previous) {
  660.         if (my_current == &my_deleted) {
  661.             newnode->previous = my_current->previous;
  662.             newnode->next = my_current->next;
  663.             my_current->previous->next = newnode;
  664.             if (my_current->next)
  665.                 my_current->next->previous = newnode;
  666.             else
  667.                 my_list->my_tail = newnode;
  668.             my_current->previous = newnode;
  669.         }
  670.         else {
  671.             newnode->previous = my_current->previous;
  672.             newnode->next = my_current;
  673.             my_current->previous->next = newnode;
  674.             my_current->previous = newnode;
  675.         }
  676.     }
  677.     else {
  678.         my_list->my_head->previous = newnode;
  679.         my_current->previous = newnode; // in case my_current = my_deleted;
  680.         newnode->next = my_list->my_head;
  681.         newnode->previous = NULL;
  682.         my_list->my_head = newnode;
  683.     }
  684.  
  685.     my_list->my_size++;
  686.     return *this;
  687. }
  688.  
  689. /****************************************************************************/
  690.  
  691. template <class Element>
  692. KPIterator<Element> &
  693. KPIterator<Element>::insert_after_current(const Element &element)
  694. {
  695.     if (!my_current)
  696.         error("insert_after_current() - no current element");
  697.     
  698.     KPList<Element>::Node *newnode = new KPList<Element>::Node;
  699.     check_mem(newnode);
  700.     newnode->element = element;
  701.  
  702.     if (my_current->next) {
  703.         if (my_current == &my_deleted) {
  704.             newnode->next = my_current->next;
  705.             newnode->previous = my_current->previous;
  706.             my_current->next->previous = newnode;
  707.             if (my_current->previous)
  708.                 my_current->previous->next = newnode;
  709.             else
  710.                 my_list->my_head = newnode;
  711.             my_current->next = newnode;
  712.         }
  713.         else {
  714.             newnode->next = my_current->next;
  715.             newnode->previous = my_current;
  716.             my_current->next->previous = newnode;
  717.             my_current->next = newnode;
  718.         }
  719.     }
  720.     else {
  721.         my_list->my_tail->next = newnode;
  722.         my_current->next = newnode;  // in case my_current == my_deleted
  723.         newnode->previous = my_list->my_tail;
  724.         newnode->next = NULL;
  725.         my_list->my_tail = newnode;
  726.     }
  727.  
  728.     my_list->my_size++;
  729.     return *this;
  730. }
  731.  
  732. /****************************************************************************/
  733.  
  734. template <class Element>
  735. KPIterator<Element> &
  736. KPIterator<Element>::replace_current_with(const Element &element)
  737. {
  738.     if (!my_current)
  739.         error("replace_current_with() - no current element");
  740.     if (my_current == &my_deleted)
  741.         error("replace_current_with() - current element has been deleted");
  742.     my_current->element = element;
  743.  
  744.     return *this;
  745. }
  746.  
  747. /****************************************************************************/
  748.  
  749. template <class Element>
  750. inline Element &
  751. KPIterator<Element>::current()
  752. {
  753.     if(!my_current)
  754.         error("current() - no current element");
  755.     return my_current->element;
  756. }
  757.  
  758.  
  759. /****************************************************************************/
  760.  
  761. template <class Element>
  762. inline Element *
  763. KPIterator<Element>::ptr()
  764. {
  765.     if (my_current)
  766.         return &my_current->element;
  767.     else
  768.         return NULL;
  769. }
  770.  
  771. /****************************************************************************/
  772.  
  773. template <class Element>
  774. Element
  775. KPIterator<Element>::remove_current()
  776. {
  777.     if (!my_current)
  778.         error("remove_current() - no current element");
  779.  
  780.     if (my_current == &my_deleted)
  781.         error("remove_current() - current element has already been removed");
  782.  
  783.     if(my_list->my_iterator_count > 1)
  784.         error("remove_current() - cannot remove element, "
  785.               "more than one iterator");
  786.  
  787.     my_deleted.element = my_current->element;
  788.     my_deleted.previous = my_current->previous;
  789.     my_deleted.next = my_current->next;
  790.  
  791.     if (my_deleted.previous)
  792.         my_deleted.previous->next = my_deleted.next;
  793.     else
  794.         my_list->my_head = my_deleted.next;
  795.  
  796.     if (my_deleted.next)
  797.         my_deleted.next->previous = my_deleted.previous;
  798.     else
  799.         my_list->my_tail = my_deleted.previous;
  800.  
  801.     my_list->my_size--;
  802.  
  803.     return my_current->element;
  804. }
  805.  
  806. /****************************************************************************/
  807.  
  808. template <class Element>
  809. inline KPIterator<Element> &
  810. KPIterator<Element>::beginning()
  811. {
  812.     if (my_list)
  813.         my_current = my_list->my_head;
  814.     return *this;
  815. }
  816.  
  817. /****************************************************************************/
  818.  
  819. template <class Element>
  820. inline KPIterator<Element> &
  821. KPIterator<Element>::end()
  822. {
  823.     if (my_list)
  824.         my_current = my_list->my_tail;
  825.     return *this;
  826. }
  827.  
  828. /****************************************************************************/
  829.  
  830. template <class Element>
  831. inline KPIterator<Element> &
  832. KPIterator<Element>::operator++()  // Prefix
  833. {
  834.     if (!my_current)
  835.         error("operator++() - no next element");
  836.  
  837.     my_current = my_current->next;
  838.     return *this;
  839. }
  840.  
  841. /****************************************************************************/
  842.  
  843. template <class Element>
  844. inline KPIterator<Element> &
  845. KPIterator<Element>::operator--()  // Prefix
  846. {
  847.     if (!my_current)
  848.         error("operator--() - no previous element");
  849.  
  850.     my_current = my_current->previous;
  851.     return *this;
  852. }
  853.  
  854. /****************************************************************************/
  855.  
  856. template <class Element>
  857. inline void
  858. KPIterator<Element>::operator++(int)  // Postfix
  859. {
  860.     if (!my_current)
  861.         error("operator++() - no next element");
  862.  
  863.     my_current = my_current->next;
  864. }
  865.  
  866. /****************************************************************************/
  867.  
  868. template <class Element>
  869. inline void
  870. KPIterator<Element>::operator--(int)  // Postfix
  871. {
  872.     if (!my_current)
  873.         error("operator--() - no previous element");
  874.  
  875.     my_current = my_current->previous;
  876. }
  877.  
  878. /****************************************************************************/
  879.  
  880. template <class Element>
  881. inline Element &
  882. KPIterator<Element>::operator*()
  883. {
  884.     if (!my_current)
  885.         error("operator*() - no current element");
  886.  
  887.     return my_current->element;
  888. }
  889.  
  890. /****************************************************************************/
  891.  
  892. template <class Element>
  893. inline Element *
  894. KPIterator<Element>::operator->()
  895. {
  896.     if (!my_current)
  897.         error("operator->() - no current element");
  898.  
  899.     return &my_current->element;
  900. }
  901.  
  902. /****************************************************************************/
  903.  
  904. template <class Element>
  905. inline bool
  906. KPIterator<Element>::at_beginning() const
  907. {
  908.     return (my_current && !my_current->previous);
  909. }
  910.  
  911. /****************************************************************************/
  912.  
  913. template <class Element>
  914. inline bool
  915. KPIterator<Element>::at_end() const
  916. {
  917.     return (my_current && !my_current->next);
  918. }
  919.  
  920. /****************************************************************************/
  921.  
  922. template <class Element>
  923. inline int
  924. KPIterator<Element>::size() const
  925. {
  926.     return my_list->size();
  927. }
  928.  
  929. /****************************************************************************/
  930.  
  931. template <class Element>
  932. inline bool
  933. KPIterator<Element>::is_empty() const
  934. {
  935.     return my_list->is_empty();
  936. }
  937.  
  938. /****************************************************************************/
  939.  
  940. template <class Element>
  941. inline KPList<Element> &
  942. KPIterator<Element>::list()
  943. {
  944.     if (!my_list)
  945.         error("list() - no list associated with iterator");
  946.  
  947.     return *my_list;
  948. }
  949.  
  950. /****************************************************************************/
  951.  
  952. template <class Element>
  953. void
  954. KPIterator<Element>::error(const char *msg)
  955. {
  956.     cerr << "KPIterator: " << msg << '\n';
  957.     exit(EXIT_FAILURE);
  958. }
  959.  
  960. /****************************************************************************/
  961.  
  962. #endif /* KP_LIST_DEFINED */
  963.